#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;

typedef int Vertex; /* 顶点编号类型 */
typedef int GElemSet; /* 边权重类型 */
typedef char VertInfo; /* 顶点信息类型 */

typedef struct EdgeNode *Position; /* 指针即结点位置 */
struct EdgeNode {
    Vertex dest; /* 边的另一端点编号 */
    GElemSet weight; /* 权重 */
    Position next; /* 线性表中下一个元素的位置 */
};
typedef struct HeadNode *AdjList; /* 邻接表 */
struct HeadNode {
    Position adj; /* 邻接表头指针 */
    VertInfo data; /* 存储顶点信息 */
};
typedef struct LGraphNode *LGraph; /* 邻接表表示的图 */
struct LGraphNode {
    int n_verts; /* 顶点数 */
    int m_edges; /* 边数 */
    AdjList *ver_list; /* 存储顶点邻接表 */
    bool directed; /* true为有向图，false为无向图 */
};
#define NIL -1 /* 顶点不存在时的返回值 */

void InitGraph(LGraph graph, int kMaxVertex, bool directed) {
    /* 初始化一个空的图 */
    Vertex v;
    Position p;

    graph->n_verts = 0;
    graph->m_edges = 0;
    /* 声明邻接表头结点数组graph->ver_list[kMaxVertex] */
    graph->ver_list = (AdjList *)malloc(sizeof(AdjList) * kMaxVertex);
    for (v = 0; v < kMaxVertex; v++) {
        graph->ver_list[v] = (AdjList)malloc(sizeof(struct HeadNode));
        graph->ver_list[v]->adj = NULL;
    }
    graph->directed = directed;
}

bool ExistEdge(LGraph graph, Vertex u, Vertex v) {
    Position p;
    bool ret = false;

    if (u < graph->n_verts && v < graph->n_verts) {
        p = graph->ver_list[u]->adj;
        while (p != NULL && p->dest != v) {
            p = p->next;
        }
        if (p != NULL) {
            ret = true;
        }
    }
    return ret;
}

void InsertEdge(LGraph graph, Vertex u, Vertex v, GElemSet weight) {
    Position p;

    if (ExistEdge(graph, u, v) == false) {
        p = (Position)malloc(sizeof(struct EdgeNode));
        p->dest = v;
        p->weight = weight;
        p->next = graph->ver_list[u]->adj;
        graph->ver_list[u]->adj = p;
        graph->m_edges++;
        if (graph->directed ==
                    false) { /* 如果是无向图，还要将u插入v的边表中 */
            p = (Position)malloc(sizeof(struct EdgeNode));
            p->dest = u;
            p->weight = weight;
            p->next = graph->ver_list[v]->adj;
            graph->ver_list[v]->adj = p;
        }
    }
}

/* 链式队列定义 */
typedef Vertex QElemSet;
#define NIL -1

typedef struct QueueNode *QPosition; /* 指针即结点位置 */
struct QueueNode {
    QElemSet data; /* 存储数据 */
    QPosition next; /* 链接队列中下一个元素的位置 */
};
typedef struct QueueHeadNode *Queue;
struct QueueHeadNode {
    int size; /* 链接队列中当前元素个数 */
    QPosition front; /* 链接队列的队首指针，初始化为NULL */
    QPosition rear; /* 链接队列的队尾指针，初始化为NULL */
};

void InitQueue(Queue queue) {
    /* 初始化一个空的链接队列 */
    queue->size = 0;
    queue->front = NULL;
    queue->rear = NULL;
}

bool IsEmpty(Queue queue) {
    /* 判断队列是否为空 */
    if (queue->size == 0)
        return true;
    else
        return false;
}

void EnQueue(Queue queue, QElemSet x) {
    QPosition new_node;

    new_node = (QPosition)malloc(sizeof(struct QueueNode));
    new_node->data = x;
    new_node->next = NULL;
    if (IsEmpty(queue)) { /* 特殊处理插入空队列的情况 */
        queue->rear = new_node;
        queue->front = new_node;
    } else {
        queue->rear->next = new_node;
        queue->rear = queue->rear->next;
    }
    queue->size++;
}

QElemSet GetFront(Queue queue) {
    if (IsEmpty(queue)) {
        printf("错误：队列为空。\n");
        return NIL;
    } else {
        return queue->front->data;
    }
}

void DeQueue(Queue queue) {
    QPosition temp;

    if (IsEmpty(queue)) {
        printf("错误：队列为空。\n");
    } else {
        temp = queue->front;
        queue->front = queue->front->next;
        free(temp);
        queue->size--;
        if (queue->front == NULL) {
            /* 特殊处理删除后变为空的队列 */
            queue->rear = NULL;
        }
    }
}

void DestroyQueue(Queue queue) {
    free(queue);
}
/* 链式队列定义结束 */

void Visit(LGraph graph, Vertex v) {
    printf("%c", graph->ver_list[v]->data);
}

/* 算法7-14: 从指定顶点开始广度优先遍历 BFSv(graph, v, visited) */
void BFSv(LGraph graph, Vertex v, bool visited[]) {
    Queue queue;
    Vertex u;
    Position p;

    queue = (Queue)malloc(sizeof(struct QueueHeadNode));
    InitQueue(queue);
    EnQueue(queue, v);
    visited[v] = true;
    while (IsEmpty(queue) == false) {
        u = GetFront(queue);
        DeQueue(queue);
        Visit(graph, u);
        p = graph->ver_list[u]->adj;
        while (p != NULL) {
            if (visited[p->dest] == false) {
                EnQueue(queue, p->dest);
                visited[p->dest] = true;
            }
            p = p->next;
        }
    }
    DestroyQueue(queue);
}
/* 算法7-14 结束 */

/* 算法7-13: 按广度优先遍历图中结点 BFS(graph) */
void BFS(LGraph graph) {
    Vertex v;
    bool *visited;

    visited = (bool *)malloc(sizeof(bool) * graph->n_verts);
    for (v = 0; v < graph->n_verts;
            v++) { /* 初始化各顶点的已访问标志为未访问 */
        visited[v] = false;
    }
    for (v = 0; v < graph->n_verts; v++) {
        if (visited[v] ==
                    false) { /* 从一个未访问的顶点开始深度优先遍历 */
            BFSv(graph, v, visited);
            printf("\n"); /* 若要求每个连通集占一行，则在行末添加回车换行 */
        }
    }
}
/* 算法7-13 结束 */

LGraph BuildGraph() {
    LGraph graph;
    int kMaxVertex, n, m, i;
    Vertex u, v;
    GElemSet weight;

    scanf("%d\n", &kMaxVertex);
    graph = (LGraph)malloc(sizeof(struct LGraphNode));
    InitGraph(graph, kMaxVertex, false);
    scanf("%d %d\n", &n, &m);
    for (v = 0; v < n; v++) {
        scanf("%c ", &graph->ver_list[v]->data);
        graph->n_verts++;
    }
    for (i = 0; i < m; i++) {
        scanf("%d %d %d\n", &u, &v, &weight);
        InsertEdge(graph, u, v, weight);
    }
    return graph;
}

int main(void) {
    LGraph graph;

    graph = BuildGraph();
    BFS(graph);

    return 0;
}